本场链接:Codeforces Round #563
本场的EF题都到了2500/2400的难度,我爬了
A. Ehab Fails to Be Thanos
题目大意:给定一个长度的序列,问你是否有可能通过重排这个序列,使得他的前个元素的和后个元素的和不一样.如果可以,则额外输出具体方案是什么.
很显然,如果整个序列排序了,则两边的和如果仍然相同,则必然是一个全相同的序列,原问题无解.否则直接输出排序后的结果就可以了.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
int a[N];
int main()
{
int n;scanf("%d",&n);
for(int i = 0;i < 2 * n;++i) scanf("%d",&a[i]);
sort(a,a + 2 * n);
int ok = 1,l = 0,r = 0;
for(int i = 0;i < n;++i) l += a[i];
for(int i = n;i < 2 * n;++i) r += a[i];
if(l == r) puts("-1");
else
for(int i = 0;i < 2 * n;++i) printf("%d ",a[i]);
return 0;
}
B. Ehab Is an Odd Person
题目大意:给一个长度为序列,对任意的两个位置,如果有是奇数,就可以交换和,问经过若干次的操作之后,可以得到的字典序最小的序列是什么.
显然,如果一个序列只有奇数或者偶数,就一下都换不了,原序列就是最小的序列了.反之,如果既有奇数又有偶数,可以发现,如果拿任意一个偶数作为跳板,就可以任意的交换所有的元素,奇数也是同理.因此如果既有奇数又有偶数,最小字典序的序列就是排序后的序列,直接输出即可.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int a[N],n;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
int odd = 0,even = 0;
for(int i = 1;i <= n;++i)
{
if(a[i] & 1) odd = 1;
else even = 1;
}
if(odd && even) sort(a + 1,a + n + 1);
for(int i = 1;i <= n;++i) printf("%d ",a[i]);
return 0;
}
C. Ehab and a Special Coloring Problem
题目大意:已知两个正整数和,对于在到之间的任意,给这个位置一个值,要满足如下两个性质:
①对于任意的两个互质的数和,需要满足.
②所有的最大值应该尽量小.
数据范围:
这题由于两两互质的条件比较强,而且暴力的判断每对数肯定是不行的.这肯定要另找出路,很容易想到筛质数里的筛法操作,这里也是同理:对于一个质数显然可以把他所有的倍数全部和他染成一个颜色,这个在筛法里套一个循环就可以了.但是怎么确定颜色有哪些呢?其实顺着上面那个思路就可以想到说:对于一个合数,他和一个质数一起一定是互质的,因此每碰到一个质数,就把染色的数字加一,再往后筛.其次如果两个合数互质的话,说明他俩里面没有相同的质因子,也就是说,他俩一定是由两个不同的质数的颜色翻上来的.所以这个方法是正确的.之后还有一步贪心也就非常顺利成章了:对于每个数,肯定只取最小的质因子染过来的色,因为要使整个序列的所有的最大值最小,可以发现这个最大值必然只是质数的个数,而且肯定也不能再减少了.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],st[N],cnt;
int col,res[N];
void init()
{
for(int i = 2;i < N;++i)
{
if(!st[i])
{
primes[cnt++] = i;
++col;
for(int j = 1;j * i < N;++j)
if(res[i * j] == 0)
res[i * j] = col;
}
for(int j = 0;j < cnt && primes[j] * i < N;++j)
{
st[primes[j] * i] = 1;
if(i % primes[j] == 0) break;
}
}
}
int main()
{
init();
int n;scanf("%d",&n);
for(int i = 2;i <= n;++i) printf("%d ",res[i]);
return 0;
}
D. Ehab and the Expected XOR Problem
题目大意:给定两个正整数和,构造一个满足如下要求的序列
①所有元素的值
②不存在一个子段的异或和是或者
③整个序列的长度要尽量长.
输出长度以及具体方案.
注意:子段的定义是把序列的开头和结尾各删掉一段连续的序列,当然可以不删,剩下的就是子段.
数据范围:
直接构造这个序列必然很困难,考虑用异或前缀和的方式曲线救国:
定义异或前缀和序列,则原有的.
其次,题目里的条件依次可以这样转换:
①的值,因为异或后的值必然不会超过,所以如此还原的序列的值最终也还是属于这个区间的.
②不存在两个相同的,以及或.因为整个子段其实就是两个前缀异或和再异或一次的结果,如果两个相同,说明这两个夹着的中间子段是,其次不能是,只要没有一个或者就可以满足不存在了.不过由于 ,所以这个条件可以不显式的写出来.
③尽量把所有满足的全填进去.
我们来考虑一下这个怎么构造的:首先肯定要把和打上标记去掉,其次,对于每一个在这个区间的值,我们都是可以加进去的,但是如果他加进去了,就不能再加了,直接标记和即可.整个流程也就非常显然了,即遍历整个范围,找到一个没标记的,把他加入序列,再把他和异或的值一起标记掉.最后还原整个序列输出即可.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 19);
int st[N];
int main()
{
int n,x;scanf("%d%d",&n,&x);
st[0] = st[x] = 1;
vector<int> res;
for(int i = 1;i < (1 << n);++i)
{
if(st[i]) continue;
res.push_back(i);
st[i] = 1;
st[i ^ x] = 1;
}
for(int i = res.size() - 1;i >= 1;--i) res[i] = res[i] ^ res[i - 1];
printf("%d\n",res.size());
for(int i = 0;i < res.size();++i)
printf("%d ",res[i]);
return 0;
}